/**
 * 104. 二叉树的最大深度
 *
 * 【简单】
 *
 * 给定一个二叉树 root ，返回其最大深度。
 * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
 *
 * 示例 1：
 * 【https://assets.leetcode.com/uploads/2020/11/26/tmp-tree.jpg】
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：3
 *
 * 示例 2：
 * 输入：root = [1,null,2]
 * 输出：2
 */

// 二叉树的深度 = 左右子树的最大深度 + 1

import { TreeNode } from '../utils/tree'

// DFS
var maxDepth = function maxDepth(root: TreeNode | null): number {
	if (root == null) {
		return 0
	}
	const leftDepth = maxDepth(root.left)
	const rightDepth = maxDepth(root.right)

	return Math.max(leftDepth, rightDepth) + 1
}

// BFS
var maxDepth = function maxDepth(root: TreeNode | null): number {
	if (root == null) {
		return 0
	}
	let res = 0
	const queue = [root]
	while (queue.length) {
		let len = queue.length
		while (len--) {
			root = queue.shift()!

			if (root.left) {
				queue.push(root.left)
			}
			if (root.right) {
				queue.push(root.right)
			}
		}

		res++
	}

	return res
}
